Reference is now made to FIG. 1 which illustrates a block diagram of a conventional cache memory 10. The memory is formed of a plurality of cache ways 12. In the example of FIG. 1, there are two cache ways 12(1) and 12(2). Thus, FIG. 1 illustrates a cache memory of the two-way set associative type as known to those skilled in the art. Each cache way 12 is formed of a plurality of cache blocks 14. There may exist n cache blocks 14 in each cache way 12 (i.e., blocks 14(1)-14(n)). Each block 14 includes a validity flag 16, a tag field 18 and a data field 20. The validity flag may, for example, comprise a size of one bit, the tag field may comprise, for example, a size of fifteen bits, and the data field may comprise, for example, a size of 128 bytes. The overall size of the cache memory 10 is calculated as the size of the cache block 14 times the number of cache blocks (n) times the number of cache ways 12.
The cache memory 10 is typically coupled to a processing system which utilizes an address 22 for memory access. The address 22 may be divided into a tag portion 24, an index portion 26 and an offset portion 28. The data within the index portion 26 of the address 22 specifies a block 14 number. The cache memory responds to the index portion 26, for example with an index value of i (in the illustrated example, i=2), by accessing the cache memory 10 at the corresponding cache block 14(i) in each of the cache ways 12.
Turning first to a read operation, comparator circuitry 30 functions to compare the data within the tag portion 24 of the address 22 to the data stored in the tag field 18 of the corresponding cache block 14(i) in each of the cache ways 12. A cache hit is indicated when the comparison is a match. In response to a match for a particular one of the cache ways 12, and assuming the validity flag 16 indicates that the data is valid, the data from the data field 20 for the cache block 14(i) in the matching one of the cache ways 12 is read out of the memory 10. If the comparator circuitry 30 fails to find a tag match, a cache miss is indicated and the cache memory 10 is bypassed.
With respect to a write operation, the memory 10 selects one of the cache ways 12 whose tag field 18 is vacant, or whose validity flag 16 indicates invalidity, and the data is written into the data field 20 of the corresponding cache block 14(i) of the selected cache way 12 and the data within the tag portion 24 of the address 22 is written into the tag field 18. In the event the cache blocks 14(i) in both cache ways 12 are occupied with valid cached data, the memory will evict data from one of the cache ways 12 to make room for the current data write. The eviction may, for example, be based on the least recently used algorithm known in the art.
The basic principal of two-way set associative cache memory configurations is that there are always two locations (one in each cache way 12 as specified by the index value of the address) for a given location in the main memory. If one of the locations is already occupied with valid data, then the other location is available. A limitation in operation occurs, however, when both locations are occupied with valid data. In such a situation, one of the locations must be overwritten using a suitable replacement algorithm. Overwriting the current contents is a multi-cycle operation because of the need to perform hit/miss detection and then perform fetch and write operations.
There is accordingly a need in the art to improve cache performance.